﻿/*----------------------------------------------------------------------------------------
*
*  Copyright 2019, Gao Hai Hui, <fromzeropoint@126.com>.  All rights reserved.
*  https://gitee.com/helloworldghh/xoskit.git
*  Use of this source code is governed by a MIT license
*  that can be found in the License file.
*
----------------------------------------------------------------------------------------*/
#ifndef __XOSKIT_XOS_CORE_XOS_STL_SRC_SETS_SETS_H__
#define __XOSKIT_XOS_CORE_XOS_STL_SRC_SETS_SETS_H__

#include "../mem_pool/head.h"

namespace xos_set
{

    //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    // 
    // sets帮助类，帮助用户建立符合sets要求的类。用户继承它就好
    // T1 : _pos_xos_stl_set_opt的类型，如int, float, double
    // T2 : _len_xos_stl_set_opt的类型，如int, float, double
    // 
    template< class T1, class T2 >
    class set_item
    {
    public:
        T1 _pos_xos_stl_set_opt;
        T2 _len_xos_stl_set_opt;
    public:
        set_item()
        {
            _pos_xos_stl_set_opt = 0;
            _len_xos_stl_set_opt = 0;
        }
        ~set_item()
        {
        }
    public:
        void _xos_stl_set_opt_init()
        {
        }
        void _xos_stl_set_opt_term()
        {
            _pos_xos_stl_set_opt = 0;
            _len_xos_stl_set_opt = 0;
        }
    };

    //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    // 比较函数

    template< class T >
    inline int compare_data( T t1, T t2 )
    {
        int nRet = 0;

        if( t1 > t2 )
        {
            nRet = 1;
        }
        else if( t1 < t2 )
        {
            nRet = -1;
        }

        return nRet;
    }

    template<>
    inline int compare_data< double >( double t1, double t2 )
    {
        int nRet = 0;

        if( t1 - t2 > 0.5 )
        {
            nRet = 1;
        }
        else if( t1 - t2 < -0.5 )
        {
            nRet = -1;
        }

        return nRet;
    }

    template<>
    inline int compare_data< float >( float t1, float t2 )
    {
        int nRet = 0;

        if( t1 - t2 > 0.5f )
        {
            nRet = 1;
        }
        else if( t1 - t2 < -0.5f )
        {
            nRet = -1;
        }

        return nRet;
    }

	//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	// 
	// T  : 有公有变量_pos_xos_stl_set_opt和_len_xos_stl_set_opt的mem_item池对象
	// T1 : _pos_xos_stl_set_opt的类型，如int, float, double
	// T2 : _len_xos_stl_set_opt的类型，如int, float, double
	// 
	template< class T, class T1, class T2 >
	class sets
	{
	public:
		typedef typename xos_stl::xos_list< T > LIST;
		typedef typename LIST::iterator ITER;
	public:
		sets();
		~sets();
	public:
		int subtract_set( LIST & dest_list, LIST & src1_list, LIST & src2_list );
		int merge_set( LIST & dest_list, LIST & src1_list, LIST & src2_list );
		int and_set( LIST & dest_list, LIST & src1_list, LIST & src2_list );
	protected:
		int subtract_set( LIST & dest_list, T * pData1, T * pData2 );
		int merge_set( LIST & dest_list, T * pData1, T * pData2 );
		int and_set( LIST & dest_list, T * pData1, T * pData2 );
		T * next( LIST & list, ITER & i );
	};

	//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	// 类实现

	template< class T, class T1, class T2 >
	sets< T, T1, T2 >::sets()
	{
	}

	template< class T, class T1, class T2 >
	sets< T, T1, T2 >::~sets()
	{
	}

	template< class T, class T1, class T2 >
	T * sets< T, T1, T2 >::next( LIST & list, ITER & i )
	{
		T * p = 0;

		if( i != list.end() )
		{
			++i;
		}

		if( i != list.end() )
		{
			p = *i;
		}

		return p;
	}

	////////////////////////////////////////////////////////////////////////////////////////////////////
	// 相减

	template< class T, class T1, class T2 >
	int sets< T, T1, T2 >::subtract_set( LIST & dest_list, LIST & src1_list, LIST & src2_list )
	{
		int nRet = 0;

		ITER i1 = src1_list.begin();
		ITER i2 = src2_list.begin();

		T * p1 = 0;
		T * p2 = 0;
		T * p = 0;

		if( i1 != src1_list.end() )
		{
			p1 = *i1;
		}
		if( i2 != src2_list.end() )
		{
			p2 = *i2;
		}

		while( ( p || p1 ) && p2 )
		{
			// 
			// 如果没有p,就准备一个p,并且跳到下一轮再进行相减动作
			// 
			if( !p )
			{
				p = T::get_item_from_pool( true );
				p->init();

				p->_pos_xos_stl_set_opt = p1->_pos_xos_stl_set_opt;
				p->_len_xos_stl_set_opt = p1->_len_xos_stl_set_opt;
				p1 = next( src1_list, i1 );

				continue;
			}

			if( compare_data( p->_pos_xos_stl_set_opt + p->_len_xos_stl_set_opt, p2->_pos_xos_stl_set_opt ) <= 0 )
			{
				dest_list.push_back( p );
				p = 0;
				continue;
			}

			// 
			// 每次循环,从src1_list或者src2_list中选择一个靠左的节点,与p进行相减
			// 
			LIST temp_list;

			// 
			// 开始相减p和pSelect
			// 
			int ret = subtract_set( temp_list, p, p2 );

			// 
			// 处理相减结果
			// 
			switch( ret )
			{
			case -2:
				{
					p->release();
					p = 0;
				}
				break;
			case -1:
				{
					T * pResult = temp_list.front();
					dest_list.push_back( pResult );
					p->release();
					p = 0;
				}
				break;
			case 0:
				{
					p2 = next( src2_list, i2 );
					p->release();
					p = 0;
				}
				break;
			case 1:
				{
					ITER i = temp_list.begin();
					T * pResult = *i++;
					p2 = next( src2_list, i2 );
					p->release();
					p = pResult;
				}
				break;
			case 2:
				{
					ITER i = temp_list.begin();
					T * pResult = *i++;
					T * pNext = *i;
					dest_list.push_back( pResult );
					p->release();
					p = pNext;
					p2 = next( src2_list, i2 );
				}
				break;
			}

			temp_list.clear();
		}

		if( p )
		{
			dest_list.push_back( p );
			p = 0;
		}

		for( ITER i = i1; i != src1_list.end(); ++i )
		{
			T * pp = *i;
			T * p = T::get_item_from_pool( true );
			p->init();
			p->_pos_xos_stl_set_opt = pp->_pos_xos_stl_set_opt;
			p->_len_xos_stl_set_opt = pp->_len_xos_stl_set_opt;
			dest_list.push_back( p );
		}

		return nRet;
	}

	// 
	// 返回值:
	// 
	// -2 --- pData2包含pData1
	// 
	// -1 --- pData1小于pData2
	// 
	// 0 --- pData1与pData2相等
	// 
	// 1 --- pData1大于pData2
	// 
	// 2 --- pData1包含pData2
	// 
	template< class T, class T1, class T2 >
	int sets< T, T1, T2 >::subtract_set( LIST & dest_list, T * pData1, T * pData2 )
	{
		int nRet = 0;

		T1 dl12 = pData1->_pos_xos_stl_set_opt + pData1->_len_xos_stl_set_opt;
		T1 dl22 = pData2->_pos_xos_stl_set_opt + pData2->_len_xos_stl_set_opt;

		T1 dl11 = pData1->_pos_xos_stl_set_opt;
		T1 dl21 = pData2->_pos_xos_stl_set_opt;

		int n11 = compare_data( dl11, dl21 );
		int n12 = compare_data( dl11, dl22 );
		int n21 = compare_data( dl12, dl21 );
		int n22 = compare_data( dl12, dl22 );

		// 
		// 1在2左边,不相交,等于pData1本身
		// 
		if( n21 <= 0 )
		{
			T * p = T::get_item_from_pool( true );
			p->init();
			p->_pos_xos_stl_set_opt = pData1->_pos_xos_stl_set_opt;
			p->_len_xos_stl_set_opt = pData1->_len_xos_stl_set_opt;
			dest_list.push_back( p );
			nRet = -1;
		}
		// 
		// 1在2右边,不相交,等于pData1本身
		// 
		else if( n12 >= 0 )
		{
			T * p = T::get_item_from_pool( true );
			p->init();
			p->_pos_xos_stl_set_opt = pData1->_pos_xos_stl_set_opt;
			p->_len_xos_stl_set_opt = pData1->_len_xos_stl_set_opt;
			dest_list.push_back( p );
			nRet = 1;
		}
		// 
		// 1与2相等,直接得空
		// 
		else if( ( n11 == 0 ) && ( n22 == 0 ) )
		{
			nRet = 0;
		}
		// 
		// 1在2内部,直接得空
		// 
		else if( ( n11 >= 0 ) && ( n22 <= 0 ) )
		{
			nRet = -2;
		}
		// 
		// 2在1内部,结果是一段或两段,因为相等的情况,上个条件判断会过滤掉
		// 
		else if( ( n11 <= 0 ) && ( n22 >= 0 ) )
		{
			if( n11 < 0 )
			{
				T * p = T::get_item_from_pool( true );
				p->init();
				p->_pos_xos_stl_set_opt = pData1->_pos_xos_stl_set_opt;
				p->_len_xos_stl_set_opt = (T2)( pData2->_pos_xos_stl_set_opt - pData1->_pos_xos_stl_set_opt );
				dest_list.push_back( p );
				nRet = -1;
			}

			if( n22 > 0 )
			{
				T * p = T::get_item_from_pool( true );
				p->init();
				p->_pos_xos_stl_set_opt = dl22;
				p->_len_xos_stl_set_opt = (T2)( dl12 - dl22 );
				dest_list.push_back( p );
				nRet = 1;
			}

			if( 2 == dest_list.size() )
			{
				nRet = 2;
			}
		}
		// 
		// 1,2相交,且1不在2内部
		// 
		else
		{
			T * p = T::get_item_from_pool( true );
			p->init();

			if( n11 < 0 )
			{
				p->_pos_xos_stl_set_opt = dl11;
				p->_len_xos_stl_set_opt = (T2)( dl21 - dl11 );
				nRet = -1;
			}
			else
			{
				p->_pos_xos_stl_set_opt = dl22;
				p->_len_xos_stl_set_opt = (T2)( dl12 - dl22 );
				nRet = 1;
			}

			dest_list.push_back( p );
		}

		return nRet;
	}

	////////////////////////////////////////////////////////////////////////////////////////////////////
	// 相合并

	template< class T, class T1, class T2 >
	int sets< T, T1, T2 >::merge_set( LIST & dest_list, LIST & src1_list, LIST & src2_list )
	{
		int nRet = 0;

		ITER i1 = src1_list.begin();
		ITER i2 = src2_list.begin();

		T * p1 = 0;
		T * p2 = 0;
		T * p = 0;

		if( i1 != src1_list.end() )
		{
			p1 = *i1;
		}
		if( i2 != src2_list.end() )
		{
			p2 = *i2;
		}

		while( p1 || p2 )
		{
			// 
			// 如果没有p,就准备一个p,并且跳到下一轮再进行合并动作
			// 
			if( !p )
			{
				p = T::get_item_from_pool( true );
				p->init();

				if( !p2 )
				{
					p->_pos_xos_stl_set_opt = p1->_pos_xos_stl_set_opt;
					p->_len_xos_stl_set_opt = p1->_len_xos_stl_set_opt;
					p1 = next( src1_list, i1 );
				}
				else if( !p1 )
				{
					p->_pos_xos_stl_set_opt = p2->_pos_xos_stl_set_opt;
					p->_len_xos_stl_set_opt = p2->_len_xos_stl_set_opt;
					p2 = next( src2_list, i2 );
				}
				else
				{
					int n11 = compare_data( p1->_pos_xos_stl_set_opt, p2->_pos_xos_stl_set_opt );

					if( n11 <= 0 )
					{
						p->_pos_xos_stl_set_opt = p1->_pos_xos_stl_set_opt;
						p->_len_xos_stl_set_opt = p1->_len_xos_stl_set_opt;
						p1 = next( src1_list, i1 );
					}
					else
					{
						p->_pos_xos_stl_set_opt = p2->_pos_xos_stl_set_opt;
						p->_len_xos_stl_set_opt = p2->_len_xos_stl_set_opt;
						p2 = next( src2_list, i2 );
					}
				}

				continue;
			}

			// 
			// 每次循环,从src1_list或者src2_list中选择一个靠左的节点,与p进行合并
			// 
			LIST temp_list;
			T * pSelect = 0;

			if( !p2 )
			{
				pSelect = p1;
				p1 = next( src1_list, i1 );
			}
			else if( !p1 )
			{
				pSelect = p2;
				p2 = next( src2_list, i2 );
			}
			else
			{
				int n11 = compare_data( p1->_pos_xos_stl_set_opt, p2->_pos_xos_stl_set_opt );

				if( n11 <= 0 )
				{
					pSelect = p1;
					p1 = next( src1_list, i1 );
				}
				else
				{
					pSelect = p2;
					p2 = next( src2_list, i2 );
				}
			}

			// 
			// 开始合并p和pSelect
			// 
			merge_set( temp_list, p, pSelect );

			// 
			// 处理合并结果
			// 
			if( 2 == temp_list.size() )
			{
				ITER i = temp_list.begin();
				T * pResult = *i++;
				T * pNext = *i;
				dest_list.push_back( pResult );
				p->release();
				p = pNext;
			}
			else if( 1 == temp_list.size() )
			{
				T * pResult = temp_list.front();
				p->release();
				p = pResult;
			}

			temp_list.clear();
		}

		if( p )
		{
			dest_list.push_back( p );
			p = 0;
		}

		return nRet;
	}

	template< class T, class T1, class T2 >
	int sets< T, T1, T2 >::merge_set( LIST & dest_list, T * pData1, T * pData2 )
	{
		int nRet = 0;

		T1 dl12 = pData1->_pos_xos_stl_set_opt + pData1->_len_xos_stl_set_opt;
		T1 dl22 = pData2->_pos_xos_stl_set_opt + pData2->_len_xos_stl_set_opt;

		T1 dl11 = pData1->_pos_xos_stl_set_opt;
		T1 dl21 = pData2->_pos_xos_stl_set_opt;

		int n11 = compare_data( dl11, dl21 );
		int n12 = compare_data( dl11, dl22 );
		int n21 = compare_data( dl12, dl21 );
		int n22 = compare_data( dl12, dl22 );

		// 
		// 1在2左边
		// 
		if( n21 < 0 )
		{
			{
				T * p = T::get_item_from_pool( true );
				p->init();
				p->_pos_xos_stl_set_opt = pData1->_pos_xos_stl_set_opt;
				p->_len_xos_stl_set_opt = pData1->_len_xos_stl_set_opt;
				dest_list.push_back( p );
			}

			{
				T * p = T::get_item_from_pool( true );
				p->init();
				p->_pos_xos_stl_set_opt = pData2->_pos_xos_stl_set_opt;
				p->_len_xos_stl_set_opt = pData2->_len_xos_stl_set_opt;
				dest_list.push_back( p );
			}
		}
		// 
		// 1在2的右边
		// 
		else if( n12 > 0 )
		{
			{
				T * p = T::get_item_from_pool( true );
				p->init();
				p->_pos_xos_stl_set_opt = pData2->_pos_xos_stl_set_opt;
				p->_len_xos_stl_set_opt = pData2->_len_xos_stl_set_opt;
				dest_list.push_back( p );
			}

			{
				T * p = T::get_item_from_pool( true );
				p->init();
				p->_pos_xos_stl_set_opt = pData1->_pos_xos_stl_set_opt;
				p->_len_xos_stl_set_opt = pData1->_len_xos_stl_set_opt;
				dest_list.push_back( p );
			}
		}
		// 
		// 1,2相交
		// 
		else
		{
			T * p = T::get_item_from_pool( true );
			p->init();

			if( n11 <= 0 )
			{
				p->_pos_xos_stl_set_opt = pData1->_pos_xos_stl_set_opt;
			}
			else
			{
				p->_pos_xos_stl_set_opt = pData2->_pos_xos_stl_set_opt;
			}

			if( n22 >= 0 )
			{
				p->_len_xos_stl_set_opt = (T2)( dl12 - p->_pos_xos_stl_set_opt );
			}
			else
			{
				p->_len_xos_stl_set_opt = (T2)( dl22 - p->_pos_xos_stl_set_opt );
			}

			dest_list.push_back( p );
		}

		return nRet;
	}

	// 
	// 相与
	// 
	template< class T, class T1, class T2 >
	int sets< T, T1, T2 >::and_set( LIST & dest_list, LIST & src1_list, LIST & src2_list )
	{
		int nRet = 0;

		ITER i1 = src1_list.begin();
		ITER i2 = src2_list.begin();

		T * p1 = 0;
		T * p2 = 0;

		if( i1 != src1_list.end() )
		{
			p1 = *i1;
		}
		if( i2 != src2_list.end() )
		{
			p2 = *i2;
		}

		while( p1 && p2 )
		{
			// 
			// 每次循环,从src1_list或者src2_list中选择一个靠左的节点,与p进行相与
			// 
			LIST temp_list;

			// 
			// 开始相与p和pSelect
			// 
			int ret = and_set( temp_list, p1, p2 );

			// 
			// 处理相与结果
			// 
			switch( ret )
			{
			case -3:
				{
					T * pResult = temp_list.front();
					p1 = next( src1_list, i1 );
					dest_list.push_back( pResult );
				}
				break;
			case -2:
				{
					T * pResult = temp_list.front();
					p1 = next( src1_list, i1 );
					dest_list.push_back( pResult );
				}
				break;
			case -1:
				{
					p1 = next( src1_list, i1 );
				}
				break;
			case 0:
				{
				}
				break;
			case 1:
				{
					p2 = next( src2_list, i2 );
				}
				break;
			case 2:
				{
					T * pResult = temp_list.front();
					p2 = next( src2_list, i2 );
					dest_list.push_back( pResult );
				}
				break;
			case 3:
				{
					T * pResult = temp_list.front();
					p2 = next( src2_list, i2 );
					dest_list.push_back( pResult );
				}
				break;
			}

			temp_list.clear();
		}

		return nRet;
	}

	// 
	// 返回值:
	// 
	// -3 --- pData1小于pData2,有相交
	// 
	// -2 --- pData2包含pData1
	// 
	// -1 --- pData1小于pData2,无相交
	// 
	// 0 --- 无意义
	// 
	// 1 --- pData1大于pData2,无相交
	// 
	// 2 --- pData1包含pData2
	// 
	// 3 --- pData1大于pData2,有相交
	// 
	template< class T, class T1, class T2 >
	int sets< T, T1, T2 >::and_set( LIST & dest_list, T * pData1, T * pData2 )
	{
		int nRet = 0;

		T1 dl12 = pData1->_pos_xos_stl_set_opt + pData1->_len_xos_stl_set_opt;
		T1 dl22 = pData2->_pos_xos_stl_set_opt + pData2->_len_xos_stl_set_opt;

		T1 dl11 = pData1->_pos_xos_stl_set_opt;
		T1 dl21 = pData2->_pos_xos_stl_set_opt;

		int n11 = compare_data( dl11, dl21 );
		int n12 = compare_data( dl11, dl22 );
		int n21 = compare_data( dl12, dl21 );
		int n22 = compare_data( dl12, dl22 );

		// 
		// 1在2左边,不相交
		// 
		if( n21 <= 0 )
		{
			nRet = -1;
		}
		// 
		// 1在2右边,不相交
		// 
		else if( n12 >= 0 )
		{
			nRet = 1;
		}
		// 
		// 1在2内部,直接得空
		// 
		else if( ( n11 >= 0 ) && ( n22 <= 0 ) )
		{
			T * p = T::get_item_from_pool( true );
			p->init();
			p->_pos_xos_stl_set_opt = pData1->_pos_xos_stl_set_opt;
			p->_len_xos_stl_set_opt = pData1->_len_xos_stl_set_opt;
			dest_list.push_back( p );
			nRet = -2;
		}
		// 
		// 2在1内部,结果是一段或两段,因为相等的情况,上个条件判断会过滤掉
		// 
		else if( ( n11 <= 0 ) && ( n22 >= 0 ) )
		{
			T * p = T::get_item_from_pool( true );
			p->init();
			p->_pos_xos_stl_set_opt = pData2->_pos_xos_stl_set_opt;
			p->_len_xos_stl_set_opt = pData2->_len_xos_stl_set_opt;
			dest_list.push_back( p );
			nRet = 2;
		}
		// 
		// 1,2相交,且1不在2内部
		// 
		else
		{
			T * p = T::get_item_from_pool( true );
			p->init();

			if( n11 < 0 )
			{
				p->_pos_xos_stl_set_opt = dl21;
				p->_len_xos_stl_set_opt = (T2)( dl12 - dl21 );
				nRet = -3;
			}
			else
			{
				p->_pos_xos_stl_set_opt = dl11;
				p->_len_xos_stl_set_opt = (T2)( dl22 - dl11 );
				nRet = 3;
			}

			dest_list.push_back( p );
		}

		return nRet;
	}

} // xos_set

#endif // __XOSKIT_XOS_CORE_XOS_STL_SRC_SETS_SETS_H__
